package com.java.comprehensive.arithmetic.leecode.medium;

import cn.hutool.core.util.ArrayUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeetCode_18 {

    public static List<List<Integer>> fourSum(int[] nums, int target) {
        quickSort(nums, 0, nums.length - 1);
        List<List<Integer>> list = new ArrayList<>();

        for (int k = 0; k < nums.length; k++) {
            if (nums[k] > target && nums[k] > 0 && target > 0) {
                return list;
            }
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.length; i++) {
                int kTemp = nums[k];
                int iTemp = nums[i];
                if (kTemp + iTemp > target && kTemp + iTemp > 0 && target > 0) {
                    break;
                }
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int l = i + 1;
                int r = nums.length - 1;
                while (l < r) {
                    int lTemp = nums[l];
                    int rTemp = nums[r];
                    long temp = (long) kTemp + iTemp + lTemp + rTemp;
                    if (temp > target) {
                        r--;
                    } else if (temp < target) {
                        l++;
                    } else {
                        list.add(Arrays.asList(kTemp, iTemp, rTemp, lTemp));
                        while (l < r && lTemp == nums[l]) l++;
                        while (l < r && rTemp == nums[r]) r--;
                    }

                }
            }
        }
        return list;
    }

    private static void quickSort(int[] nums, int l, int r) {
        if (l >= r) {
            return;
        }
        //确定中心轴
        int pivot = nums[l];
        int left = l;
        int right = r;
        while (l < r) {
            while (l < r && nums[r] >= pivot) {
                r--;
            }
            nums[l] = nums[r];
            while (l < r && nums[l] <= pivot) {
                l++;
            }
            nums[r] = nums[l];
        }
        nums[l] = pivot;
        quickSort(nums, left, l - 1);
        quickSort(nums, r + 1, right);
    }

    public static void main(String[] args) {
        int[] nums = {1, 0, -1, 0, -2, 2};
        List<List<Integer>> list = fourSum(nums, 0);
        System.out.println(ArrayUtil.toString(list));
    }
}
